// 89. 格雷编码
// https://leetcode.cn/problems/gray-code/
// 递归 动态规划

/**
示例 1：

输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同
示例 2：

输入：n = 1
输出：[0,1]
 */

/**
 * @param {number} n
 * @return {number[]}
 */
var grayCode = function (n) {
    let binArr = backTracking(n);
    console.log(`${n} is ${JSON.stringify(binArr)}`);

    const digitArr = binArr.map((ele) => parseInt(ele, 2));

    console.log(`${n} is ${JSON.stringify(digitArr)}`);

    return digitArr;
};

function backTracking(n) {
    if (n === 0) {
        return ['0'];
    }

    if (n === 1) {
        return ['0', '1'];
    }

    let arr = backTracking(n - 1);
    let arr_reverse = [].concat(arr).reverse();

    let ret = arr
        .map((ele) => '0' + ele)
        .concat(arr_reverse.map((ele) => '1' + ele));

    return ret;
}

grayCode(0);
grayCode(1);
grayCode(2);
grayCode(3);
